:- module(tp2, [distHam/3, distPref/3, distEd/3]).


elemValido(0).
elemValido(1).

entre(X, Y, X) :- X =< Y.
entre(X, Y, Z) :- X < Y, N is X+1, entre(N, Y, Z).

desde(X, X).
desde(X, Y) :- N is X + 1, desde(N, Y).

cadenaValidaDeLong([],0).
cadenaValidaDeLong([X|Xs],N) :-
    cadenaValidaDeLong(Xs,N1),
    elemValido(X),
    N is N1 + 1.

cadenaValidaDeLongNG([],0).
cadenaValidaDeLongNG([X|Xs],N) :-
    N > 0,
    elemValido(X),
    N1 is N - 1,
    cadenaValidaDeLongNG(Xs, N1).

prefijoComunMasLargo([], [], []).
prefijoComunMasLargo([_|Xs], [], []) :- prefijoComunMasLargo(Xs, [], []).
prefijoComunMasLargo([], [_|Xs], []) :- prefijoComunMasLargo([], Xs, []).
prefijoComunMasLargo([X|_], [Y|_], []) :- X \= Y.
prefijoComunMasLargo([X|Xs], [Y|Ys], [Z|Zs]) :-  X = Y, X = Z, prefijoComunMasLargo(Xs, Ys, Zs).

% Distancia de Hamming
distHam([], [], 0).
distHam([X|Xs], [X|Ys], N) :- distHam(Xs, Ys, N).
distHam([X|Xs], [Y|Ys], N) :- X \= Y, distHam(Xs, Ys, NAnt), N is NAnt + 1.


% Distancia de Prefijos
% distPref(+L1, ?L2, ?L3)
distPref(X, Y, N) :- ground(N),
	cadenaValidaDeLong(X,Nx),
	Nmax is Nx + N,
	entre(0, Nmax, Ny),
	cadenaValidaDeLongNG(Y,Ny),
	prefijoComunMasLargo(X, Y, Z), 
	cadenaValidaDeLong(Z, Nz), 
	N is (Nx - Nz) + (Ny - Nz).
distPref(X, Y, N) :- not(ground(N)),
	cadenaValidaDeLong(X,Nx),
	cadenaValidaDeLong(Y,Ny),
	prefijoComunMasLargo(X, Y, Z), 
	cadenaValidaDeLong(Z, Nz), 
	N is (Nx - Nz) + (Ny - Nz).


% Distancia de Edición
% Operación de inserción
operacionBasica(L1, L2) :- elemValido(X), select(X, L2, L1).
% Operación de modificación
operacionBasica(L1, L2) :- append(Inicio, [Y | Fin], L1), elemValido(X), X \= Y, append(Inicio, [X | Fin], L2).
% Operación de eliminación
operacionBasica(L1, L2) :- elemValido(X), select(X, L1, L2).

% nOperacionesBasicas(+L1, ?L2, +N)
nOperacionesBasicas(L1, L2, 0) :- cadenaValidaDeLong(L1,N1),
		   cadenaValidaDeLongNG(L2,N1),	
		   L1 = L2.
nOperacionesBasicas(L1, L2, N) :- N > 0,operacionBasica(L1, L3), Nant is N-1, nOperacionesBasicas(L3, L2, Nant),!.

sonTodasVariablesYValido([]).
sonTodasVariablesYValido([X|Xs]) :- var(X), sonTodasVariablesYValido(Xs).
sonTodasVariablesYValido([X|Xs]) :- not(var(X)), elemValido(X), sonTodasVariablesYValido(Xs).

% distEd(+S, ?T, ?D)
distEd(X, T, 0) :- 
		cadenaValidaDeLong(X,Nx),                
		   cadenaValidaDeLongNG(T,Nx),	
		   T = X.
distEd(X, T, N) :- ground(N), N > 0,
		   cadenaValidaDeLong(X,Nx),
		   Ncotas is N + Nx,
		   entre(0, Ncotas, Nt),
		   cadenaValidaDeLongNG(T,Nt),
		   nOperacionesBasicas(X,T,N),
		   Nant is N - 1,
                   forall(entre(0,Nant, N1), not(nOperacionesBasicas(X,T,N1))).
distEd(X, T, N) :- not(ground(N)), ground(T),
		   cadenaValidaDeLong(T,Nt),
		   cadenaValidaDeLong(X,Nx),
		   Ncotas is Nt + Nx,
		   entre(1, Ncotas, N),
		   nOperacionesBasicas(X,T,N),!.
distEd(X, T, N) :- not(ground(N)), not(ground(T)), 
		 cadenaValidaDeLong(X,Nx),
		   sonTodasVariablesYValido(T),
		   cadenaValidaDeLong(T,Nt),
		   Ncotas is Nt + Nx,
		   entre(0,Ncotas,N),
		   nOperacionesBasicas(X,T,N),
		   Nant is N - 1,
                   forall(entre(0,Nant, N1), not(nOperacionesBasicas(X,T,N1))).


		  
